package com.hdu.other.dp.one;

public class lc983 {
    class Solution {

        int[] durations = new int[]{1, 7, 30};

        public int mincostTickets(int[] days, int[] costs) {
            int[] dp = new int[days.length + 1];
            for (int i = 0; i <= days.length; i++)
            {
                dp[i] = -1;
            }
            return f(
                    days,
                    costs,
                    0,
                    dp
            );
        }

        /**
         来到第 i 天 花销最小是多少？
         */
        int f(int[] days, int[] costs, int index, int[] dp)
        {
            if (index >= days.length)
            {
                return 0;
            }
            if (dp[index] != -1)
            {
                return dp[index];
            }
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < 3; i++)
            {
                int curCost = costs[i];
                int curDuration = durations[i];
                int curDay = days[index];
                int j = i;
                while (j < days.length && curDay + curDuration > days[j])
                {
                    j++;
                }
                /**
                 j == days.length
                 curDay + curDuration <= days[j]
                 */
                ans = Math.min(
                        ans,
                        curCost + f(days, costs, j, dp)
                );
            }
            return dp[index] = ans;
        }
    }
}
